#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct QUEUE Queue;
typedef struct BINTREE BT;
typedef char NodeType;
typedef BT*  ElementType;
struct QUEUE{
	ElementType Elm;
	Queue *Next;
	Queue *Tail;
};
struct BINTREE{
	NodeType Node;
	BT *Left;
	BT *Right;
};

Queue* QueueInit(void);
_Bool  QueueEmpty(Queue*);
void   EnQueue(Queue*,ElementType);
ElementType DeQueue(Queue*);
BT *BuildTree(int n,char*);
void MidOrder(BT *root);
void PostOrder(BT *root);

int main(){
	char c[]="ABCDFGI00E00H";
	BT *t=BuildTree(strlen(c),c);
	printf("String Len:%3ld\n",strlen(c));
	MidOrder(t);
	printf("\n");
	PostOrder(t);
	return 0;
}
Queue* QueueInit(void){
	Queue *q=malloc(sizeof(Queue));
	q->Next=NULL;
	q->Tail=q;
	return q;
}
_Bool  QueueEmpty(Queue* q){
	if( q->Next )
		return false;
	return true;
}
void   EnQueue(Queue* q,ElementType x){
	Queue *new=malloc(sizeof(Queue));
	new->Elm=x;
	new->Next=NULL;
	q->Tail->Next=new;
	q->Tail=new;
	return;
}
ElementType DeQueue(Queue* q){
	Queue *t=q->Next;
	ElementType e=t->Elm;
	q->Next=t->Next;
	free(t);
	if( !q->Next )
		q->Tail=q;
	return e;
}
BT *NewNode(NodeType x){
	BT *new=malloc(sizeof(BT));
	new->Node=x;
	new->Left=new->Right=NULL;
	return new;
}
BT *BuildTree(int n,char *ch){
	int i=-1;
	BT *tree=NULL;
	BT *current=NULL;
	Queue *father=QueueInit();
	if( '0' != ch[++i] ){
		tree=NewNode(ch[i]);
		EnQueue(father,tree);
	}
	while( !QueueEmpty(father) ){
		current=DeQueue(father);
		if( i>=n-1 || ch[++i] == '0' ){
			current->Left=NULL;
		}else{
			current->Left=NewNode(ch[i]);
			EnQueue(father,current->Left);
		}
		if( i>=n-1 || ch[++i] == '0' ){
			current->Right=NULL;
		}else{
			current->Right=NewNode(ch[i]);
			EnQueue(father,current->Right);
		}
	}
printf("i:%d\n",i);
	return tree;
}
void MidOrder(BT *root){
	if( root ){
		MidOrder(root->Left);
		printf("| %-3c :%d |",root->Node,root->Node);
		MidOrder(root->Right);
	}else{
		//printf("%3s","NL");
	}
	return;
}
void PostOrder(BT *root){
	if( root ){
		PostOrder(root->Left);
		PostOrder(root->Right);
		printf("| %-3c :%d |",root->Node,root->Node);
	}else{ 
		//printf("N  ");
	}
	return;
}
